class SPACE

Definition (space-bounded computation)

Let $S : \mathbb{N} \to \mathbb{N}$ and $L \in \{0,1\}^*$. Say that language $L \in \mathbf{SPACE}(s(n))$ if there is a constant $c$ and TM $M$ deciding $L$ such that at most $c \cdot s(n)$ locations on $M$'s work tapes (excluding input tape) are ever visited by $M$'s head during computation on every input of length $n$.

Notes

• Similarly, NSPACE for NDTM

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 78-79.